home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Chip 1996 April
/
CHIP 1996 aprilis (CD06).zip
/
CHIP_CD06.ISO
/
hypertxt.arj
/
92
/
ORA_ELJ.CD
< prev
next >
Wrap
Text File
|
1995-09-14
|
11KB
|
290 lines
@VEljuthatunk-e az órától Einsteinig, avagy megfejtések
áprilistól májusig@N
@VAz óra...@N
Åprilisi számunkban jelent meg @KAz óra és Einstein@N címû
fejtörônk, amelynek lényege, hogy mikor és hányszor vannak
egy hagyományos (és jól mûködô) órán az óramutatók olyan
helyzetben, hogy felcserélésükkel egy másik lehetséges
helyzetet (valós, értelmezhetô idôpontot) kapjunk meg.
A feladatra kilenc megoldás érkezett, közülük nyolc
bizonyult helyesnek. Megoldóink sokféle nyelvet használtak
(Pascal, Basic, Clipper, assembly stb.), de lényegében
hasonló utat jártak végig. Rövid matematikai megfontolás
után a ""favágó" munkát (azaz a keresett idôpontok
elôállítását) a gépre bízták. Az egyik lehetséges
matematikai gondolatmenetet Gáldonyi Béla megoldása alapján
foglaljuk össze:
Ha a kismutató a kiindulási helyzethez képest (ez legyen
12 óra) @Kfi@N szöggel elfordul, akkor a nagymutató az
alaphelyzethez képest @K12*fi@N szöget zár be. A mutatók cseréje
az jelenti, hogy a kismutató szöge lesz @K12*fi@N, míg a
nagymutató által bezárt szög @K12*12*fi@N-re változik. Mármost
ez csak akkor tekinthetô cserének, ha a nagymutató új
helyzete megegyezik a kismutató régi állásával. Ez
egyenletben így írható le:
@K144*fi = fi + k*2*pi@N
ahol a @Kk*2*pi@N jelzi, hogy a nagymutató @Kk@N darab teljes
kört tett meg közben. Az egyenlet megoldása:
@Kfi = k/143 * 2*pi@N
Mivel a kismutató egy körét vizsgáljuk (azaz
@K0<=fi<2*pi@N), ezért @Kk= 0, 1, 2, ..., 143@N. Hogy a 12 órát ne
számoljuk kétszer, a @Kk@N értékénél el kell hagynunk valamelyik
határt. Ezek után már tényleg csak a kulimunka marad: a
mellékelt Basic program (Rákos Péter munkája) elôállítja a
keresett idôpontokat.
A programok közötti apróbb különbségeket elsôsorban a
kapott 143 megoldás megjelenítési módja okozta. Volt aki
képernyôre, volt aki nyomtatóra, volt aki file-ba ""terelte"
a végeredményt.
E fordulóban a szerencse Gáldonyi Bélának kedvezett,
nyereménye egy csomag Tungsram floppy.
@VEljutunk-e...@N
Májusi számunkban jelent meg elôször ""emeletes"
rejtvény, a módosított játékszabályoknak megfelelôen.
A ""földszinti" feladat így hangzott: adott @KN@N település,
amelyek mindegyikérôl tudjuk, hogy melyik másikkal állnak
közvetlen közlekedési összeköttetésben. îrjunk olyan
programot, amely megadja, hogy egy @KA@N faluból/városból
eljuthatunk-e egyáltalán egy @KB@N településre.
Hét helyes megoldás érkezett határidôre. A nyelvek
nemhivatalos versenyében újfent a Pascal nyert, dobogós
versenytársai a Prolog és a Modula voltak. A feladat egy
lehetséges megoldását régi rendszeres megfejtônk, mondhatni
szerzônk, Gyombolai Márton részletes dokumentációja alapján
vázoljuk.
Legyen egy @Kn*n@N-es logikai tömbünk (@KUT@N), amelyben az
@K(i,j)@N elem igaz, ha van közvetlen út az @Ki@N-edik faluból a
@Kj@N-edikbe, egyébként hamis. A kérdés az, hogy el lehet-e
jutni @Kn1@N-bôl @Kn2@N-be.
Elsô lépésben jelöljük ki azt a @KH1@N halmazt, amely
azokból a falvakból áll, ahová @Kn1@N-bôl egy lépésben el lehet
jutni. Ha @Kn2@N benne van @KH1@N-ben, akkor máris készen vagyunk.
Ha @KH1@N üres halmaz (@Kn1@N-bôl sehová nincs út), akkor nincs
megoldás, illetve az a megoldás, hogy nincs út @Kn1@N-bôl @Kn2@N-be.
Második lépésben azt a @KH2@N halmazt jelöljük ki, amelybe
azok a falvak tartoznak, ahová még nem jutottunk el (nem
@KH1@N-beli és nem @Kn1@N), de @KH1@N-bôl egy lépésben elérhetô. A
@KH2@N-ben így épp azok a települések lesznek, amelyek @Kn1@N-bôl
pontosan két lépésben érhetôk el. Ha @Kn2@N eleme @KH2@N-nek, akkor
készen vagyunk. Ha @KH2@N üres halmaz (vagyis nincs ilyen falu),
akkor nincs út @Kn2@N-be. És így tovább...
A fenti lépéseket maximum @Kn-1@N-ig tudjuk folytatni,
hiszen egy falu csak egyetlen halmazban lehet benne. Ha @Kn2@N
egyiknek sem eleme, akkor nincs út.
Megfejtônk mellékelt programjában halmazok helyett (az
egyszerûség kedvéért) egy @KLEPES@N nevû, @Kn@N elemû tömböt
használ, úgy, hogy @KLEPES(x)=i@N, ha az @Kx@N falu a @KHi@N halmazba
tartozik. A @KLEPES@N elnevezést az indokolja, hogy @KHi@N elemei
éppen azok a falvak, ahová @Ki@N lépésben lehet eljutni.
Fortuna e fordulóban Horváth Sándor barcsi megfejtônket
részesítette kegyeiben, övé a doboznyi Tungsram floppy.
@VLegrövidebb idô alatt...@N
Az ""emeleti" rejtvény az elôzô finomításából adódott:
az N településrôl azt is tudjuk, hogy a meglévô közvetlen
összeköttetések mekkora menetidôt jelentenek. îrjunk egy
olyan programot, amely megadja a legkisebb idôt igénybe vevô
utat @KA@N és @KB@N települések között -- ha létezik ilyen.
A feladat e (némileg nehezített) változatára kilenc
megoldás érkezett, többségükben olyanoktól, akik az elsô
variációt is megoldották -- ami érthetô, ha figyelembe
vesszük a két kérdés rokonságát. Kérdés persze, hogy kinél
melyik változat volt az elsô, s adódott esetleg egyszerû
melléktermékként a másik megoldás.
A szoros rokonság okán folytassuk Gyombolai Márton
gondolatmenetét, aki maga is utal arra, hogy a második
feladat megoldása jól ráépíthetô az elsôre. Itt persze nem
logikai, hanem tényleges úthosszakat tartalmazó integer
tömböt kell használnunk, -1 értékkel ott, ahol nincs
közvetlen út.
A korábbi algoritmusnak az a fô baja, hogy egy kevesebb
lépésszámú út hosszabb lehet egy több lépésesnél. Ezen úgy
segíthetünk, hogy egyrészt nemcsak a lépésszámot tároljuk,
hanem a tömbben azt is, hogy az @Kn1@N-tôl az @Ki@N-ig megtett
távolság mekkora. Másrészt a halmazokat is másként kell
képezni: @KHi@N-be azok a falvak tartoznak, amelyek egyfelôl egy
@KHi-1@N-beli faluból egy lépésben elérhetôk, és másfelôl
-- vagy még nem jutottunk el ide (@Khi@N-be) sehogyan
sem;
-- vagy most a régi útnál rövidebb úton jutottunk el
ide.
Fontos változás, hogy itt egy @KHi@N-be sorolt falu késôbb
átkerülhet egy @KHj@N halmazba @K(j>i)@N, ha rövidebb (bár több
lépéses) utat leltünk. Ezért nem is állhatunk meg azonnal,
amint eljutunk @Kn2@N-be, hiszen még rövidebb utat is
találhatunk (@Kn2@N is átkerülhet másik @KH@N halmazba).
A változatosság kedvéért nem a fenti algoritmust
megvalósító Pascal programot közöljük (melyet az eddigiek
alapján vállalkozó kedvû olvasónk viszonylag könnyen
megírhatnak), hanem Déri Attila Prolog nyelvû programjának
fix adatokkal dolgozó változatát. Érdemes tanulmányozni!
(Emlékeztetôül: e kategóriában most nem, hanem majd
decemberben sorsolunk, rendszeres megoldóink között.)
@KBánhegyesi Zoltán@N
program vaneut1;
{Gyombolai Márton}
var
i,j,lep,innen,ide,n,n1,n2: integer;
ures, keszjo: boolean;
ut: array[1..100,1..100] of boolean;
lepes: array[1..100] of integer;
Procedure Beolvas;
var vane:integer;
begin
write('Faluk száma=');
readln(n);
for i:= 2 to n do
for j:= 1 to i-1 do
begin
write(i:3,' és ',j:3, ' közt van út? 1, ha igen, 0, ha nem! ');
readln(vane);
ut[i,j] := (vane=1); {Illenék mindenfélét ellenôrizni,}
ut[j,i] := (vane=1); {de itt nem ez a lényeg.}
end;
for i:=1 to n do ut[i,i] := false;
end;
Procedure Kiir;
begin
if keszjo
then writeln('Van megoldás ',lep-1:3,' lépésben!')
else writeln('NINCS MEGOLDÅS!');
end;
begin
Beolvas;
write('Az induló falu sorszáma: ');
readln(n1);
while n1 > 0 do
begin
write('A cél-falu sorszáma: ');
readln(n2);
for i:=1 to n do lepes[i] := -1;
lepes[n1] := 0;
keszjo := false;
lep := 1;
repeat
ures:= true;
for innen := 1 to n do
begin
if lepes[innen] = lep-1 {Ha INNEN-be az elôzô lépésben }
then {jutottunk el }
if ut[innen,n2]
then keszjo := true {Találtunk utat! }
else
for ide := 1 to n do
if lepes[ide] = -1 {Ha IDE még nem jutottunk el...}
then begin
ures := false;
if ut[innen,ide] {...de most igen, }
then lepes[ide] := lep; {akkor ez LEP lépéses út }
end;
end;
lep := lep+1;
until (lep > n-1) or ures or keszjo;
Kiir;
write('Az induló falu sorszáma: ');
readln(n1);
end;
end.
CLS
PRINT " FI ORA PERC MASODPERC ORA PERC MASODPERC"
FOR i = 1 TO 143
fi = i * 12 / 143: a = fi
h = INT(fi): fi = fi - h: fi = fi * 60
min = INT(fi): fi = fi - min
sec = INT(fi * 60): fi = a
PRINT fi, h
PRINT " "; min
PRINT " "; sec,
PRINT " "; h + 12; " "; min
PRINT " "; sec
NEXT
/* A lehetô leggyorsabban...? */
/* Járatok a programban beépítve */
/* Készítette: Déri Attila */
domains
lista=string*
database
tarol(integer, integer, lista)
predicates
berak(integer, lista)
ut(lista, string, string, integer)
kapocs(string, symbol, integer)
kapcs(string, string, integer)
nincs(lista, string)
kiir(lista)
megnez
clauses
ut(L, X, X, I):-berak(I, [X|L]), !, fail.
ut(L, X, Y, I):-kapocs(X, Z, K), nincs(L, Z),
J=I+K, ut([X|L], Z, Y, J).
nincs([], _).
nincs([X|_], X):-!, fail.
nincs([_|L], X):-nincs(L, X).
berak(J, L):-tarol(1, I, _), J<I,
retract(tarol(1, _, _)),
assert(tarol(1, J, L)).
megnez:-tarol(1, _, []),
write("Nem talaltam osszekottetest!"), nl, !.
megnez:-tarol(1, I, L),
write(I, " idoegyseg alatt megteheto utat talaltam: "),
kiir(L), write("."), nl,
retract(tarol(1, _, _)).
kiir([]):-!.
kiir([X|L]):-L=[], write(X).
kiir([X|L]):-kiir(L), write(", ", X).
kapocs(X, Y, I):-kapcs(X, Y, I).
kapocs(X, Y, I):-kapcs(Y, X, I).
kapcs("Baja", "Mohacs", 7).
kapcs("Baja", "Szekszard", 5).
kapcs("Mohacs", "Pecs", 6).
kapcs("Szekszard", "Pecs", 15).
kapcs("Baja", "Szeged", 9).
kapcs("Bekescsaba", "Szeged", 9).
kapcs("Bekescsaba", "Kecskemet", 12).
kapcs("Kecskemet", "Szeged", 9).
kapcs("Budapest", "Kecskemet", 8).
kapcs("Kecskemet", "Baja", 11).
kapcs("Nagykanizsa", "Szekesfehervar", 13).
kapcs("Szekesfehervar", "Veszprem", 6).
kapcs("Veszprem", "Szombathely", 11).
kapcs("Nagykanizsa", "Szombathely", 11).
goal
assert(tarol(1, 10000, [])), write("Honnan: "),
readln(X), write("Hova :"), readln(Y),
ut([], X, Y, 0); megnez.